import java.util.*;

public class Ford_Fulkerson {
	
	public static int maxFlow (Vertex src, Vertex des, SimpleGraph g)
	{
		int maxflow=0;
		
		Iterator itr = g.edgeList.iterator();	//set capacity, all flows=0
		while (itr.hasNext()){
			Edge e = (Edge)itr.next();
			EdgeData ed = new EdgeData( ( (Double)e.getData() ).intValue() );
			ed.flow = 0;
			e.setData(ed);
		}
		
		VertexData noVisit;
		noVisit=new VertexData(null,false);
		
		//find augmenting path, update flows
		while (true){
			
			itr = g.vertexList.iterator();	//set all vertex !visit
			while(itr.hasNext()){
				((Vertex)itr.next()).setData(noVisit);
			}
			
			DFS(src, des);
			if( ((VertexData)des.getData()).visited==false ){
				break; //end while loop if can't find augmenting path
			}
			
			int increment = Integer.MAX_VALUE;
			int value = Integer.MAX_VALUE;
			Vertex tmp = des;
			
			
			while (tmp!=src){	//find increment
				Iterator eitr1 = tmp.incidentEdgeList.iterator();
				while (eitr1.hasNext()){
					Edge etmp = (Edge)eitr1.next();
					if( etmp.getFirstEndpoint()==((VertexData)tmp.getData()).prev ){
						value = ((EdgeData)etmp.getData()).capacity
								- ((EdgeData)etmp.getData()).flow;
						break;
					}
				}
				
				tmp = ((VertexData)tmp.getData()).prev;
				increment = Math.min(increment, value); 
			}
			
			tmp=des;
			while (tmp!=src){	//update flow
				Iterator eitr = tmp.incidentEdgeList.iterator();
				while (eitr.hasNext()){
					Edge etmp = (Edge)eitr.next();
					
					if( etmp.getFirstEndpoint()==((VertexData)tmp.getData()).prev ){
						int x = ((EdgeData)etmp.getData()).flow + increment;
						int y = ((EdgeData)etmp.getData()).capacity;
						EdgeData ed = new EdgeData (x,y);
						etmp.setData(ed);
					}
				}
				tmp = ((VertexData)tmp.getData()).prev;
			}
			maxflow += increment;
		}
		
		return maxflow;
	}
	
	public static void DFS (Vertex src, Vertex des)
	{
		VertexData visit=new VertexData(((VertexData)src.getData()).prev, true);
		src.setData(visit);
		
		Iterator itr = src.incidentEdgeList.iterator();
		while (itr.hasNext()){
			Edge e = (Edge)itr.next();
			
			if(e.getFirstEndpoint()==src && ((VertexData)e.getSecondEndpoint().getData()).visited!=true 
					&& ((EdgeData)e.getData()).capacity-((EdgeData)e.getData()).flow>0){
				VertexData vd = new VertexData(src,true);
				e.getSecondEndpoint().setData(vd);
				DFS(e.getSecondEndpoint(), des);
			}
		}
	}
	
	public static void run (String file) {
        SimpleGraph G = new SimpleGraph();
        GraphInput gi = new GraphInput();
        Hashtable table = new Hashtable();
        
        table = gi.LoadSimpleGraph(G, file);
        Vertex src, des,test;
        src = (Vertex)table.get("s");
        des = (Vertex)table.get("t");
        
        long start=System.currentTimeMillis();
        System.out.println("MaxFlow = " + maxFlow(src,des,G));
        System.out.println("Run time = " +(System.currentTimeMillis()-start)+ "ms\n");
  }
	
	public static void main(String args[])
	{
		run("so10_si20_p1_c10_c10.txt");
	}
}